/*
 * Copyright 2012 Alain Pannetrat (L1L1@gmx.com)
 * 
 * This file is part of cookie-miner.
 * 
 * cookie-miner is free software: you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation, either version 3 of the License, or 
 * (at your option) any later version.
 * 
 * cookie-miner is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License 
 * along with cookie-miner. If not, see http://www.gnu.org/licenses/.
 *
 * @version: $Id$
 *
 */
#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_

#include <string>

template<typename T>
class Dictionary {
	public:
		static T TNull;

		class Item {
			public:
				Item() {}

				void init(const std::string &skey, const T& sval, unsigned shash) { 
					_key = skey; _val = sval; _hash=shash; }

				const std::string& key() const { return _key; }
				//void key(const std::string &skey) { _key = key; _hash=hash_key(skey); }

				const T& val() const { return _val; }
				void val(const T& sval) { _val = sval; }

				unsigned hash() const { return _hash; }
				//void hash(unsigned shash) const { _hash = shash; }

				bool empty() { return _key.size()==0; }
				void clear() { _key.clear(); }

				// auto constructors are fine //
			private:
				std::string _key;
				T _val;
				unsigned _hash;
		};

		class Iterator {
			public:
				Iterator(unsigned size=0, Item* dict=NULL) : 
					_size(size), _dict(dict) { }

				const Item& get() const { return _dict[_pos]; }

				const Iterator& next() {  
					do _pos++; while(_pos<_size && _dict[_pos].empty()); return *this; }

				const Iterator& operator++() {
					return next(); }	

				bool operator==(const Iterator& it) {
					return _dict == it._dict && _pos == it._pos; }
				bool operator!=(const Iterator& it) {
					return _dict != it._dict || _pos != it._pos; }

			private:
				friend class Dictionary;

				Iterator& rewind() {
					_pos = 0; if (_dict && _dict[_pos].empty()) next(); return *this; }

				Iterator& forward() {
					_pos = _size; return *this; }

				unsigned _pos;
				unsigned _size;
				Item* _dict;
		};

		class Reference {
			public:
				Reference(Dictionary<T>* dict, std::string &index) : 
					_dict(dict), _index(index) {}
				const T& operator=(const T& val) const { 
					if (_dict->set(_index,val)) return val; return TNull; }
				// default copy constructor is OK
			private:
				Dictionary<T>* _dict;
				const std::string& _index;
				const Reference& operator=(const Reference&); // = 0
		};

		Dictionary() : _top(7), _count(0) { _dict = _default_dict; }

		Iterator begin() const 	{ Iterator it(_top+1,_dict); return it.rewind(); }
		Iterator end() const 	{ Iterator it(_top+1, _dict); return it.forward(); }

		bool set(const std::string& key, const T& val);

		bool get(const std::string& key, T& val) const;

		const T& operator[](const std::string& key) const;

		Reference operator[](const std::string& key) { 
			return Reference(this,key); }

		bool exists(const std::string& key) const { 
			unsigned h = hash_key(key);
			return (!_dict[find_slot(key,h)].empty()); }

		unsigned size() const { return _count; } 
		
		void clear() { 
			_count = 0; for (unsigned i=0;i<=_top;i++) _dict[i].clear(); }

#ifdef _TEST_DICTIONARY_H_
		void dump();
#endif

		~Dictionary() { }
	private:
		unsigned hash_key(const std::string& key) const;
		unsigned find_slot(const std::string& key, unsigned) const;

		void rescale(unsigned new_size);

		unsigned _top;
		unsigned _count;
		Item* _dict;
		Item  _default_dict[8];
};

/*****************************************
 * 
 * Template implementation
 *
 */

template<class T>T Dictionary<T>::TNull = T(0);

template<class T>
bool Dictionary<T>::set(const std::string& key, const T& val) 
{
	unsigned slot;
	unsigned h;

	if (key.size()==0)
		return false;

	h = hash_key(key);
	slot = find_slot(key,h);

	if (_dict[slot].empty())
	{
		if (_count>2*_top/3) 
		{
			rescale((_top+1)*2);
			return set(key,val);
		}
		_dict[slot].init(key,val,h);
		_count++;
		return true;
	}
	else
	{	
		_dict[slot].val(val);
	}
	return true; 
}

template<class T>
bool Dictionary<T>::get(const std::string& key, T& val) const 
{
	unsigned slot;
	unsigned h;

	if (key.size()==0) 
		return false;

	h = hash_key(key);
	slot = find_slot(key,h);

	if (_dict[slot].empty()) return false;

	val = _dict[slot].val();

	return true; 
}

template<class T>
const T& Dictionary<T>::operator[](const std::string& key) const 
{
	unsigned slot;
	unsigned h;

	if (key.size()==0) 
		return TNull;

	h = hash_key(key);
	slot = find_slot(key,h);

	if (_dict[slot].empty()) 
		return TNull;

	return _dict[slot].val(); 
}

template<class T>
inline unsigned Dictionary<T>::hash_key(const std::string& key) const 
{
// the classic sdbm hash
	unsigned h = 0;

	for (unsigned i=0;i<key.size();i++) 
		h=key[i]+(h<<16)+(h<<6)-h;

	return h; 
}

template<class T>
unsigned Dictionary<T>::find_slot(const std::string& key, unsigned h) const 
{
	h = h & _top;

	while (!_dict[h].empty()) {
		if (_dict[h].key() == key)
			return h;
		h = (h+1)&_top;
	}
	return h; 
}

template<class T>
void Dictionary<T>::rescale(unsigned new_size) 
{
	Item* old_dict = _dict;
	unsigned old_top = _top;
	unsigned slot;

	_dict = new Item[new_size];
	_count = 0;
	_top = new_size-1;
	for (unsigned i=0;i<=old_top;i++) if (!old_dict[i].empty()) 
	{
		slot = find_slot(old_dict[i].key(),
				 old_dict[i].hash());
		_dict[slot].init(old_dict[i].key(),
				 old_dict[i].val(),
				 old_dict[i].hash());
		_count++;
	}
	if (old_dict!=_default_dict)
		delete [] old_dict; 
}

#ifdef _TEST_DICTIONARY_H_
#include <stdio.h>
template<class T>
void Dictionary<T>::dump() 
{
	for (unsigned i=0;i<=_top;i++)
	{
		fprintf(stderr,"[%02i] hash={%10u,%2u} - %s\n",
				i,
				_dict[i].hash(),_dict[i].hash()&_top,
				_dict[i].key().c_str());
	}
}
#endif
#endif
